1. Field
The following relates to systems and methods for performing encryption and more particularly to systems and methods for performing encryption on a platform on which an attacker has privileges, such as privileges to observe execution or modify execution of an encryption algorithm.
2. Related Art
Many encryption algorithms are primarily concerned with producing encrypted data that is resistant to decoding by an attacker who can interact with the encryption algorithm as a “black box” model, and cannot observe internal workings of the algorithm, or memory contents, and so on. A black box model may be appropriate for applications where trusted parties control machines involved both in encoding and in decoding ciphered materials.
However, many applications of encryption do not allow for an assumption that an attacker cannot view internal workings of the algorithm. For example, encrypted digital media often needs to be decrypted on systems that are completely controlled by an adversary. There are many degrees to which the black box model can be relaxed. An extreme relaxation is called the “white box” model. In a white box model, it is presumed that an attacker has total access to a system performing an encryption, including being able to observe directly a state of memory, program execution, and so on. In such a model, an encryption key can be observed in/extracted from memory, and so ways to conceal operations indicative of a secret key are important.
The Advanced Encryption Standard (AES) is a well-known symmetric key block cipher. There are a variety of references that describe it, for example, “Advanced Encryption Standard” Wikipedia, The Free Encyclopedia (available at http://en.wikipedia.org/aes).
To implement AES (128 bit blocks, 10 rounds) arithmetically involves the following operations: (1) 11 AddRoundKey operations (1 prior to 10 rounds), (2) 10 SubByte operations, (3) 10 ShiftRow Operations, and (4) 9 MixColumn Operations. Each round of rounds 1-9 consists of (1)-(4), where output from one step is input to the next step, and output from (4) is input to (1). Round 10 consists of (1)-(3), where output from (3) is the output used. Arithmetic implementations of AES do not provide much security against an attacker recovering a secret key, if the attacker has privileged access to the system implementing the cipher.
The reference “White-Box Cryptography and an AES implementation” Lecture Notes in Computer Science Vol. 2595, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography pp. 250-270 (2002) by Chow et al. (Chow) discloses implementations of AES that obscures the operations performed during AES by using table lookups to obscure the secret key within the lookup tables, and obscure intermediate state information that would otherwise be available in arithmetic implementations of AES.
Chow uses 160 separate tables to implement the 11 AddRoundKey operations and 10 SubByte Operations (10 rounds, with 16 tables per round, where each table is for 1 byte of the 16 byte—128 bit—AES block). These 160 tables embed a particular AES key, such that output from lookups involving these tables embeds data that would normally result from the AddRoundKey and SubByte operations of the AES algorithm, except that this data includes errors that make it more difficult to determine what parts of these tables represent round key information derived from the AES key.
Chow uses 1008 separate tables to implement the 9 MixColumn Operations (there is no MixColumn operation in the 10th round of AES). One type of these tables implements a multiplication of one byte with the AES MixColumn polynomial (per the specification), and another type implements the XOR part of MixColumn. Each table is used once during the 9 rounds.
Collectively, these tables require over 400 KB to store, which is a large memory footprint. Chow does not disclose smaller memory footprint whitebox implementations, or implementations that are more scalable. Thus, it would be desirable to have white box functionality for encryption algorithms with a smaller memory footprint, and/or which provide better scalability.